
//力扣113. 路径总和 II

import java.util.*;
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root==null){
            return res;
        }
        if(root.val==targetSum&&root.left==null&&root.right==null){
            path.add(root.val);
            res.add(path);
            return res;
        }
        func(root,targetSum,res,path,0,1);
        return res;
    }
    public void func(TreeNode root, int targetSum,List<List<Integer>> res,List<Integer> path,int Sum,int index){
        if(root==null){
            return;
        }
        path.add(root.val);
        func(root.left,targetSum,res,path,Sum+root.val,index+1);
        func(root.right,targetSum,res,path,Sum+root.val,index+1);
        if(Sum+root.val==targetSum&&index!=1&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(path));
        }
        path.remove(path.size()-1);
    }

}





/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }

 */

//牛客网NC198 判断是不是完全二叉树
 class Solution1 {

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                //遇到null就break出循环
                break;
            }
        }
        //遍历看队列是否有不是null的
        while (!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            //如果有不是null的，就返回false
            //不让就出队列
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }
}





/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

//牛客网:按之字形顺序打印二叉树
class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(pRoot==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(pRoot);
        boolean flag=true;
        while(!queue.isEmpty()){
            int n = queue.size();
            ArrayList<Integer> path=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode temp=queue.poll();
                path.add(temp.val);
                if(temp.left!=null) {
                    queue.offer(temp.left);
                }
                if(temp.right!=null) {
                    queue.offer(temp.right);
                }
            }

            if(!flag){
                Collections.reverse(path);
            }
            res.add(path);
            flag=!flag;
        }
        return res;
    }

}